package search;

import java.util.Arrays;
import java.util.Random;

import movgen.Move2;
import movgen.Util;
import myEngine.Engine2;
import state.GameState;
import state.PawnStructureTable;

public class Search2 extends Thread{
	
	public static final int MAX_DEPTH=200;
	
	private static final int MOVEGEN_CHECK_EVASION_PHASE = 4;
	private static final int MOVEGEN_HASHMOVE2_PHASE = 3;
	private static final int MOVEGEN_NONCAPTURES_PHASE = 2;
	private static final int MOVEGEN_CAPTURES_PHASE = 1;
	private static final int MOVEGEN_HASHMOVE_PHASE = 0;

	public static final int INVALID_MOVE = -1;
	
	//pondering
	//public static int ponderMove = INVALID_MOVE;

	//TIME
	private static boolean usingTime=true;

	private static final double LEVEL_INCREASE_TIME_MULTIPLE = 2.0;
	public static final int TIME_CHECK_INTERVAL = 1000; // How often we should check if time is up inside alphaBeta
	public static int  nextTimeCheck = TIME_CHECK_INTERVAL;
	public static int movesPerSession=0;   //default
	public static int movesMade=0;
	public static long baseTime=0;     // in milliseconds; default = 15 minutes
	public static long increment=0;

	public static long timeLeft=0;     //time left for the player
	public static long opponentTimeLeft=0;     // time left for the opponent
	public static long timeForThisMove;
	public static boolean  stopSearch = true;
	public static long startTime=0;
	
	//END TIME

	private static final int CAPTURE_SORT_VALS=32;

	public static final int TO_SHIFT = 6; // Number of bits to shift to get the to-index
	public static final int PIECE_SHIFT = 12; // To get the piece moving
	public static final int CAPTURE_SHIFT = 16; // To get the capture
	public static final int TYPE_SHIFT = 20; // To the move type
	public static final int ORDERING_SHIFT = 25; // To get the ordering value

	public static final int SQUARE_MASK = 63; // 6 bits, masks out the rest of the int when it has been shifted so we only get the information we need
	public static final int PIECE_MASK  = 15; // 4 bits
	public static final int TYPE_MASK = 31; // 5 bits
	public static final int ORDERING_CLEAR = 0x1FFFFFF; // = 00000001111111111111111111111111 use with & which clears the ordering value

	private static final int MAX_INFINITY = 500000;
	private static final int MIN_INFINITY = -500000;
	private static int depthLevel=0;
	private static final int MATE=100000;
	public static int valWINDOW=35;
	private static int nodesSearched=0,
			numQuiesNodes=0,
			usingHashMove=0,
			futilityPrune=0;
	private static final int R = 2;     // used for null move
	private static final int FullDepthMoves = 4;
	private static final int ReductionLimit = 3;
	private static final int MAXDEPTH=20;

	private static int[][][] history= new int[2][64][64];
	private static final int NO_HISTORY_SORT_VAL = 63;  
	private static final int HISTORY_POINTS = 30;

	//put it in the end if no history - if we do see we should change this to 62, because bad captures get 63

	private static final int NUMKILLERS=2;

	private static int[][] killer=  new int[MAXDEPTH][NUMKILLERS];
	private static boolean 
			useIID,do_LMR,  
			extensionsOn, futilityOn,aspirationOn, 
			turnNullOn,deltaPruneOn,positionalEvalOn,orderByHistory,
		    orderByKillers,turnSEEOn;
			

	public static boolean foundMove=false;
	public static boolean ponder=false;

	private static boolean debug=false;
	public static boolean isDebug() {
		return debug;
	}
	public static void setDebug(boolean debug) {
		Search2.debug = debug;
	}
	private static Random  rnd= new Random();

	private static void clearHistory() {
		for (int i=0 ; i < 2; i++) {
			for (int j=0; j < 64; j++) {
				for (int k=0; k < 64; k++) {
					history[i][j][k]=0;
				}
			}
		}
	}

	private static void turnEverythingOn() {
		useIID=true;
		TranspositionTable.useTT=true;
		do_LMR=true;
		extensionsOn=true;
		futilityOn=true;
		aspirationOn=true;
		turnNullOn=true;
		positionalEvalOn=true;
		deltaPruneOn=true;
		orderByKillers=true;
		orderByHistory=true;
		turnSEEOn=true;
	}
	
	private static void initGlobals() {
		zeroOutCounters();
		
		turnEverythingOn();
		
		GameState.resetMoveHistory();
	}
	private static void zeroOutCounters() {
		nodesSearched=0;
		numQuiesNodes=0;
		stopSearch=false;
		usingHashMove=0;
		futilityPrune=0;
		TranspositionTable.stores=0;
		
		int x = rnd.nextInt();
		if (x % 4 ==0 ) clearHistory();
		for (int i=0; i < MAXDEPTH; i++) {
			for (int j=0; j < NUMKILLERS; j++) {
				killer[i][j]=0;
			};
		}
	}
	
	public  static String calcBestMove(GameState state, int depthLevel2) {
		depthLevel=depthLevel2;
		initGlobals();

		int move = calcBestMove(state, depthLevel, MIN_INFINITY, MAX_INFINITY);
		movesMade++;
		return Move2.toString(move);
	}

	private  static MoveInfo[] makeMoveInfo(int[] movelist) {
		MoveInfo[] mi = new MoveInfo[movelist.length];

		for (int i=0; i < movelist.length; i++) {
			mi[i] = new MoveInfo(movelist[i],0);
		}
		return mi;
	}

	public  static  int calcBestMove(GameState state, int depthlevel, int alpha, int beta)  {

		int    bestMove=0;   
		
		int[] movelist;
		
		boolean ownKingInCheck=state.isInCheck( state.color);
		if (ownKingInCheck)
			movelist=state.generateCheckEvasionMoves(state.color);
		else
			movelist=  state.getAllMoves();
		
		MoveInfo[] movelist2 = makeMoveInfo(movelist);

		int flags2=state.flags;
		long hash=state.hash;

		int currentDepth=1;

		int maxIterations=depthLevel;
		if (usingTime) {
			maxIterations=MAXDEPTH;
		}

		if (usingTime) {
			startTime=System.currentTimeMillis();
			timeForThisMove = TimeControl.getTimeForThisMove(timeLeft, movesPerSession- ( ( movesMade + Engine2.numBookMovesMade) % movesPerSession ), increment);
		}
		int bestScoreForThisIteration = 0;
		
		while (currentDepth < maxIterations) {

			// we don't have enough time to do this iteration, so return the global best move
			if (usingTime) {
				if((System.currentTimeMillis() - startTime) * LEVEL_INCREASE_TIME_MULTIPLE > timeForThisMove) {
					if (debug) printLoggingInfo(currentDepth, bestMove, bestScoreForThisIteration);
					return bestMove;
				}
			}

			bestScoreForThisIteration= MAX_INFINITY;
			Arrays.sort(movelist2);

			
			for (int i=0; i< movelist2.length; i++)
			{
				int move = movelist2[i].move;
				int moveType = Move2.moveType(move);
				if (!isLegal(state, move, flags2, hash, moveType)) continue;
		

				int searchDepth=currentDepth;
			
				int score;
				score = search(state, alpha, beta,  searchDepth,MATE,true,false, false);
				
				if (usingTime && stopSearch) {
					state.unmake(move, flags2, hash);
					break;
				}

				movelist2[i].value=score;

				state.unmake(move, flags2, hash);

				/*if (currentDepth >= 6 && debug) 
					System.out.println("Level " + currentDepth + "   " + Move2.toString(move) +
							" value " + score + " bestval "
							+ bestScoreForThisIteration + " alpha " + alpha + " beta " + beta);
*/
				if (score < bestScoreForThisIteration) {
					bestScoreForThisIteration=score;
					bestMove=move;

					if (score <= alpha) {
						alpha=score;
					if (score < beta) break;
					}
				}

			}// end processing all moves loop

			if (aspirationOn) {
				if (bestScoreForThisIteration <= alpha) {
					alpha = MIN_INFINITY;
					continue;
				}
				else  
					if  (bestScoreForThisIteration >= beta) {
					beta = MAX_INFINITY;
					continue;
				}
				alpha = bestScoreForThisIteration - valWINDOW;
				beta = bestScoreForThisIteration + valWINDOW;
			}
			
			currentDepth++;
		}  //end of iteration deepening loop

		
		if (debug) printLoggingInfo(currentDepth, bestMove, bestScoreForThisIteration);
		
	
		//ponderMove=getPonderMove(state, bestMove);
		
		return bestMove;
	}
	
	/*private static int getPonderMove(GameState state, int bestMove) {
		// apply bestMove to state
		// Then try to find the opponents response in the transposition table
		// It may or may not exist. If it does, and it is legal in the position, we can ponder on it.
		GameState gs = new GameState(state);
		gs.make(bestMove);
		long hash=gs.hash;
		
		if (TranspositionTable.useTT) {
			boolean found = TranspositionTable.probeHash(state.hash);               // *** check if this position was visited before, and if we still have info about it
		
			if(found) {                                   // *** position was searched before, and found in the table
				bestMove = TranspositionTable.getMove(hash)  ; 
				if (state.isMoveLegal(bestMove)) {
					System.out.println("Ponder move= " + Move2.toString(ponderMove));
					return bestMove;
				}
				else {
					System.out.println("Ponder move found, but not legal");
				}
			}
			else {
				System.out.println("No Ponder move found");
			}
		}
		return INVALID_MOVE;
	}*/
	private static void printLoggingInfo(int currentDepth, int bestMove, int score) {
		StringBuffer sb = new StringBuffer();
		sb.append("bestmove " + Move2.toString(bestMove) +  " score " + score + 
		             " currentDepth " + currentDepth + " time for this move " + timeForThisMove + 
				" Num regular nodes  = " + nodesSearched + "   numQuiesNodes " + numQuiesNodes); 
		sb.append("\n");
		long totalNodes = nodesSearched + numQuiesNodes;
		sb.append(
				" total  nodes  = " + totalNodes ); 
		sb.append("\n");
		sb.append(" probes " + TranspositionTable.probes + " hits " + TranspositionTable.hits + " repetitions " + TranspositionTable.repetitionsFound) ; 
		sb.append("  Using hash values " + usingHashMove);
		sb.append("\n");
		sb.append("hashtable hit rate " + (float)TranspositionTable.hits / (float)TranspositionTable.probes +
				" stores = " + TranspositionTable.stores );
		sb.append("\n");
		sb.append("futility Prunes " + futilityPrune);
		sb.append("\n");

		sb.append("passed pawn table : stores= " + 
				PawnStructureTable.stores + "  probes   "  + PawnStructureTable.probes + " hits" + PawnStructureTable.hits);
		
		sb.append("\n");
		if (debug)
		  System.out.println(sb.toString());
		else
		  Engine2.debug(sb.toString());
	}

	private static boolean isLegal (GameState state, final int move, int flags2, long hash, int moveType) {

		if (moveType == Move2.kcastle || moveType == Move2.qcastle) {    //castling
			if (state.isInCheck( state.color)) {
				return false;
			}
			state.make(move);
			// you cannot make a move that puts yourself in check
			if (state.isInCheck(  1- state.color)) {
				state.unmake(move, flags2, hash);

				return false;
			}
			if (state.isInCheck( 1-state.color)) {
				state.unmake(move, flags2, hash);
				return false;
			}
			if (state.isInCheck(  GameState.minedBitboards[1-state.color][moveType-2],  state.color) )  {
				state.unmake(move, flags2, hash);
				return false;
			}
		}
		else {
			state.make(move);
			// you cannot make a move that puts yourself in check
			if (state.isInCheck(  1- state.color)) {
				state.unmake(move, flags2, hash);

				return false;
			}
		}
		return true;
	}
	
	
	/*  ALPHA BETA   ( Comment by Harm Geert Muller )
	 * 
	 * Some branches need not be searched, because whatever their score,
	 *  one of the players will get a better one by deviating from it earlier.
This is expressed by the 'search window' {alpha, beta}:
 in any node, alpha is the score of the best move for the current side to move that has
  already been found in any of the nodes on the path leading to (and including) the current node. 
  Beta is the same for the opponent, but seen from the current mover's POV. 
  If a move scores below alpha, we are not interested how much below alpha it scores, as we are not going to play it, 
  because we already did have a fully verified move that scores alpha, and will prefer that.
  
   If we have a move that scores above beta, it is not important how much above beta it scores,
    as our score above beta for the opponent looks as a score below his alpha,
which is the situation described in the previous sentence: 
he will now prefer the verified move that scores beta (from our POV), 
so we will never get the chance to play the move that (for us) scored above it.

So we can stop searching alternative moves from a position as soon as we find one move
 that scores above beta.
 
  This move is then a refutation of the opponent's preceding move, which is apparently so bad he is never going to play it. 
  Trying to show it is even more bad is a waste of time, so we will abort the search of that node at this point. 
  This is called a beta cutoff.

This sounds pretty complex, but the program that does it is actually quite simple.
 Every time we find a better move, we increase alpha.
This is passed to all daughter nodes, which, two ply later, will include their best moves in it (if they are even better), etc. In the intermediate node this our alpha becomes the opponent's beta (after the sign flip to effect the change in POV characteristic of negamax), and finally passed to the grand-children of the current node as alpha again:
	 * 
	 */
	private static int search(GameState state, int alpha, int beta,
			int depth, int mate, boolean allowNull, boolean extended, boolean returnBestMove)   
	{
		
		if (usingTime) {
			nextTimeCheck--;
			if(nextTimeCheck == 0) // Time to check the time
			{
				nextTimeCheck = TIME_CHECK_INTERVAL;
				if((System.currentTimeMillis() - startTime) > timeForThisMove)
				{
					stopSearch = true;
					return 0;
				}
			}
		}
		long hash=state.hash;
	
		boolean foundPv=false;

		boolean ownKingInCheck=state.isInCheck( state.color);
		
		if (depth == 0) {

			if ( (extensionsOn) && (!extended) && ( state.promotion || state.seventhRankExtension
					|| state.isSameSquareRecapture() || ownKingInCheck))
			{

				depth++;
				extended = true;
			}
			else{
				return quies(state,alpha,beta,depth);
			}
		}

		int bestScore = MIN_INFINITY;
		int bestMove = INVALID_MOVE;

		//null move; ( not allowed when in check )
		/****************************************************************
		 *   This comment ( but not the code) is from CPW- engine
		 *  null move pruning:  allowing   *
		 *  opponent  to  execute two moves in a row,  i.e.  capturing   *
		 *  something  and escaping a recapture. If this cannot  wreck   *
		 *  our  position,  then it is so good that there's  no  point   *
		 *  in searching further. The flag allowNull ensures we don't   *
		 *  do  two null moves in a row. Null move is not used in  the   *
		 *  endgame because of the risk of zugzwang.                     *
		 ****************************************************************/
		if  ( turnNullOn && (!ownKingInCheck) && allowNull  && ((depth - 1 - R) > 2) && (!state.isEndGame())) {
			state.color = 1-state.color;
			if ( state.color==GameState.BLACK) state.hash = state.hash ^ GameState.side;

			int nullMoveScore = -search(state, -beta, -beta + 1,depth - 1 - R,  mate-1, false,false,false);

			state.color = 1-state.color;
			if ( state.color==GameState.BLACK) state.hash = state.hash ^ GameState.side;

			if (nullMoveScore >= beta) {

				if (TranspositionTable.useTT) {
					TranspositionTable.hashStore(state.hash, depth, bestMove,bestScore, alpha, beta); 
					// *** alpha and beta are needed to determine meaning of score (bound type)
				}

				return beta;
			}            	
		}
		
		/****************************************************************
		 * COMMENT from CPW engine
		 *  If  depth  is too low for a null move pruning,  decide  if   *
		 *  futility  pruning is  applicable. If we are not  in  check,  *
		 *  not searching for a checkmate and eval is well below alpha,  *
		 *  it  might  mean that searching non-tactical moves  at  low   *
		 *  depths is futile, so we set a flag allowing this pruning.    *
		 ****************************************************************/
		// Futility pruning
		boolean fprune = false;
		int fmargin = 0;
		int materialEval = 0;
		
		if   ( (depth ==1 && !ownKingInCheck)){
			materialEval =state.getEvaluationMaterial();
			
			if (materialEval + 200  <= alpha){
				fmargin = 200;
				fprune = true;
			}
		}

		if (TranspositionTable.useTT) {
			boolean found = TranspositionTable.probeHash(state.hash);               // *** check if this position was visited before, and if we still have info about it
		
			if(found) {     
				// *** position was searched before, and found in the table
				if (TranspositionTable.isRepetition(state.hash)) {
					TranspositionTable.repetitionsFound++;
					return 0;
				}
					
				else
				if(TranspositionTable.usefulScore(hash, alpha, beta)) {       // *** upper/lower bound might be useless with current {alpha, beta}
					bestScore = TranspositionTable.getScore(hash);         
				}
				bestMove = TranspositionTable.getMove(hash)  ;                  // *** use move anyway, for lack of a better alternative
			}
		}
		 /*---------------------------------------------------------
		   | Internal iterative deepening: if this is a PV node and |
		   | there is no best move from the hash table, then do a   |
		   | shallow search to find a best move to search first.    |
		   ---------------------------------------------------------*/
		if ( (useIID ) && ( alpha != beta+1 ) && ( bestMove == INVALID_MOVE) && (depth > 3)  )  {
			 bestMove = search(state, alpha, beta,
						depth - 2, mate, allowNull, extended, true)   ;
		}
		
		int[] movelist =null;
		int legal=0;
		int flags2=state.flags;
		int childrenSearched=0;
		int movegen_phase= MOVEGEN_HASHMOVE_PHASE;
		int lastMovegen_phase=MOVEGEN_NONCAPTURES_PHASE;
		
		if (ownKingInCheck) {
			movegen_phase=MOVEGEN_HASHMOVE2_PHASE;
			lastMovegen_phase=MOVEGEN_CHECK_EVASION_PHASE;
		}
		
		boolean hashFound=false;
		
		outerloop:
			while ( movegen_phase <= lastMovegen_phase)
			{
				switch(movegen_phase) {

				case MOVEGEN_HASHMOVE_PHASE:	//normal
				case MOVEGEN_HASHMOVE2_PHASE:   // for check evasions
					if (bestMove != INVALID_MOVE) {
						if ( state.isMoveLegal(bestMove)) {
							movelist= new int[1];
							movelist[0]=bestMove;
							usingHashMove++;
							hashFound=true;
						}
						else {
							movegen_phase++;
							continue;
						}
					}
					else {
						movegen_phase++;
						continue;
					}
					break;

				case MOVEGEN_CAPTURES_PHASE:
					movelist =state.generateCapturesAndPromotions(state.color);
					if (movelist.length > 0 ) {
					
						orderMovesCaps(state, movelist,hash,depth, bestMove, hashFound);
					}

					break;
				case MOVEGEN_NONCAPTURES_PHASE:
					movelist= state.generateNonCaptures(state.color);
					if (movelist.length > 0 ) {
						
						orderMoves(state, movelist,depth, bestMove, hashFound);
					}
					break;
				case MOVEGEN_CHECK_EVASION_PHASE:
					movelist=state.generateCheckEvasionMoves(state.color);
					if (movelist.length > 0 ) {
					
						orderMoves(state, movelist,depth, bestMove, hashFound);
					}
				break;
				}
		
				//GameState gs2= new GameState(state);
				for (int i=0; i< movelist.length; i++)
				{                         
					int move=movelist[i];
					if (move==0) continue;
					int moveType = Move2.moveType(movelist[i]);

					if (!isLegal(state, move, flags2, hash, moveType)) continue;
					
					legal++;
					boolean opponentIsInCheck = state.isInCheck(state.color);

					// Futility pruning, 
					/********************************************************************
					 *  When the futility pruning flag is set, prune moves which do not  *
					 *  give  check and do not change material balance. 
					 ********************************************************************/
					
					if (futilityOn && fprune && (childrenSearched > 0)) {
						if (!opponentIsInCheck) {
							if (isCapture(move)) {
								materialEval += GameState.valueMap[Move2.capture(move)];
							}
							if((materialEval+fmargin) <= alpha) {
								futilityPrune++;
								state.unmake(move, flags2, hash);
								//if (!gs2.equals(state)) error(gs2,state, move);
								continue;
							}
						}  
					}
					int score;
					int searchDepth=depth-1;

					//late move reduction ? Here is where the idea is from: http://www.glaurungchess.com/lmr.html
					int orderingValue=Move2.orderingValue(move);
					
					if (do_LMR) {
						score = lmr_search(state, alpha, beta, depth, mate,
								extended, legal, opponentIsInCheck, searchDepth,
								orderingValue);
					}
					else {
						score = pv_search(state, alpha, beta, mate, extended,
								foundPv, searchDepth);
					}
				
					nodesSearched++;
					childrenSearched++;

					state.unmake(move, flags2, hash);
					//if (!gs2.equals(state)) error(gs2,state, move);
					
					if(score > bestScore) 
					{                  // *** score accounting: remember best (from side-to-move POV)
						bestScore = score;

						if(score > alpha) {                    // *** narrow search window for remaining moves
							alpha = score;
							bestMove = move;
							foundPv = true;
						
							if(score >= beta)  {
								if ( moveType < 10 )   // not a capture or promotion
								{
									updateKillerAndHistory(state, depth, move);
								}
								break outerloop;             // *** beta cutoff: previous ply is refuted by this move, so we can stop here to take that back
							}
						}
					}
				} // next move
				movegen_phase++;
			}  // next phse
		if (legal == 0) {
			if (! state.isInCheck( state.color) )  {
				return 0;
			}
			return -mate;                 // Checkmate.
		}
		if (TranspositionTable.useTT) {
			TranspositionTable.hashStore(hash, depth, bestMove,bestScore, alpha, beta); 
			// *** alpha and beta are needed to determine meaning of score (bound type)
		}
		if (returnBestMove)
			return bestMove;
		return bestScore;

	}
	
	private static int pv_search(GameState state, int alpha, int beta,
			int mate, boolean extended, boolean foundPv, int searchDepth) {
		int score;
		if (foundPv) {
			score = -search( state,  -alpha - 1, -alpha, searchDepth,mate - 1, true,extended, false);   // reduced window pv search
			if ((score > alpha) && (score < beta)) // Check for failure.
				score = -search(state,  -beta, -alpha,searchDepth, mate - 1, true,extended, false);   // do regular search
		}
		else {
			score = -search(state,  -beta, -alpha,searchDepth, mate - 1, true,extended, false);   // do regular search
		}
		return score;
	}
	private static int lmr_search(GameState state, int alpha, int beta,
			int depth, int mate, boolean extended, int legal,
			boolean opponentIsInCheck, int searchDepth, int orderingValue) {
		int score;
		if (legal == 1) {
			score = -search(state, -beta, -alpha,searchDepth, mate - 1, true,extended, false);        //normal alpha-beta search
		}
		else 
		{
			if ( (!extended) && (legal >= FullDepthMoves) && (depth >= ReductionLimit)  
					&& (orderingValue >= CAPTURE_SORT_VALS + 1) 
					&& (!opponentIsInCheck) && ( beta - alpha <= 1)) 
			{
				score = -search( state,  -alpha - 1, -alpha, searchDepth-1,mate - 1, true,extended, false);   // reduced window pv search
			}
			else 
			{
				 score = alpha+1;  // Hack to ensure that full-depth search is done.
			}
			if(score > alpha) 
			{
				score = -search( state,  -alpha - 1, -alpha, searchDepth,mate - 1, true,extended, false);   // reduced window pv search
				if ((score > alpha) && (score < beta)) // Check for failure.
					score = -search(state,  -beta, -alpha,searchDepth, mate - 1, true,extended, false);   // do regular search
		    } 
		}
		return score;
	}

	private static void updateKillerAndHistory(GameState state, int depth,
			int move) {
		int f = Move2.fromIndex(move);
		int t = Move2.toIndex(move);

		if (history[state.color][f][t] < HISTORY_POINTS) 
			history[state.color][f][t] ++;

		int killerValue=killer[depth][0];

		if (killerValue == 0 ) {
			killer[depth][0]=move;
		}
		else {
			killer[depth][1]=killerValue;
			killer[depth][0]=move;
		}
	}
	/***************************************************************
	 *  At leaf nodes we do quiescence search                       *
	 *  to make sure that only relatively quiet positions           *
	 *  with no hanging pieces will be evaluated.                   *
	 ***************************************************************/
	private static int quies( GameState state, int alpha, int beta, int depth)
	{
		/*if (  state.isInCheck(  state.color) ) {
			return search(state,  alpha, beta, 1, MATE,false,false,false);
		}*/
		/*
		 * 
		 */
		int val ;
		
		if (positionalEvalOn)
			val= state.getEvaluation();
		else
			val=state.getEvaluationMaterial();

		if (val >= beta) {
			return beta;
		}
		if (val > alpha) {
			alpha = val;
		}
		int[] movelist = state.generateCapturesAndPromotions(state.color);
		if (movelist.length==0 ) return val;

		if (turnSEEOn)
			orderMovesQuies(state, movelist);
		else 
			Util.sort(movelist);

		long hash = state.getHash();
		int flags2=state.flags;

		for (int i=0; i< movelist.length; i++)
		{
			int move = movelist[i];
			if (move==0) continue;
			state.make(move);
			numQuiesNodes++;
			if (  state.isInCheck( 1-state.color) ) {
				state.unmake(move, flags2, hash);
				continue;
				// you cannot put yourself in check
			}

			val = -quies( state, -beta, -alpha,  depth-1);
			state.unmake(move, flags2, hash);
			if (val >= beta) {
				return beta;
			}

			// The next three lines test if alpha can be improved by greatest
			// possible matrial swing. This is called delta pruning

			if (!state.isEndGame() && deltaPruneOn) {
				int BIG_DELTA = GameState.QUEEN_VALUE; // queen value
				if (state.promotion) BIG_DELTA += (GameState.QUEEN_VALUE - GameState.PAWN_VALUE) ;

				if ( val < alpha - BIG_DELTA ) {
					return alpha;
				}
			}

			if (val > alpha)
				alpha = val;
		}
		return alpha;
	}
	private static boolean orderMovesCaps(GameState state, int[] movelist, long hash, int depth, int hashMove, boolean hashFound) {

		if (hashFound) {
			for (int i=0; i < movelist.length; i++)
			{
				int move = movelist[i];
				if (hashMove==move) {
					movelist[i] = 0;   // we already searched it, so set to zero
					break;
				}
			}
		}

		Util.sort(movelist);
		return hashFound;
	}
	private static void orderMoves(GameState state, int[] movelist, int depth, int hashMove, boolean hashFound) {


		for (int i=0; i < movelist.length; i++)
		{
			int move = movelist[i];

			if ( (hashMove==move) && (hashFound)) {
				movelist[i]=0;
				continue;
			}
			int type =((move >> TYPE_SHIFT) & TYPE_MASK);

			if (type < 6 ) // simple, castling, or pawn push
			{
				boolean killerFound=false;

				if (orderByKillers) {
					for (int j=0; j< NUMKILLERS; j++) {
						if (move == killer[depth][j]) {
							
							movelist[i] = (movelist[i] & ORDERING_CLEAR); // Clear the ordering value
							movelist[i] = (movelist[i] | ((CAPTURE_SORT_VALS + 1) << ORDERING_SHIFT)); // Change the ordering value and return the new move integer
							killerFound=true;
							break;
						}
					}
				}
				
				if (killerFound) continue;  //if not, try history

				if (orderByHistory) {
					int from =  (move & SQUARE_MASK);
					int to = ((move >> TO_SHIFT) & SQUARE_MASK);	
					// lets order these from 33 to 127
					int historyVal = history[state.color][from][to];
					if (historyVal > 0) {
						if (historyVal > HISTORY_POINTS) historyVal=HISTORY_POINTS;
						int sortval= Math.min(NO_HISTORY_SORT_VAL,  CAPTURE_SORT_VALS + 2 + (HISTORY_POINTS - historyVal));
						//movelist[i] = Move2.setOrderingValue ( move, sortval);
						movelist[i] = (movelist[i] & ORDERING_CLEAR); // Clear the ordering value
						movelist[i] = (movelist[i] | ( sortval << ORDERING_SHIFT)); // Change the ordering value and return the new move integer

					}
				}
				
			}
		}
		Util.sort(movelist);
	}

	private static void  orderMovesQuies(GameState state, int[] movelist) {
		int newValue2=INVALID_MOVE, newValue=INVALID_MOVE;

		for (int i=0; i < movelist.length; i++)
		{
			int move = movelist[i];
			int type = ((move >> TYPE_SHIFT) & TYPE_MASK);
			
			if (type == Move2.captureNoPromotion) {          //capture with promotion already was given a good ordering in movegen
				int orderingValue=Move2.orderingValue(move);
				// we don't want to waste time by doing a SEE on cheap attackers with expensive victims ( idea from Robert Hyatt/ Crafty )
				switch(orderingValue) {      // the following are cases of relatively expensive attackers versus victims ie; R X b
				case 27: case  28: case 29: case 23: case 17: case 30: case 24: case 12: case 18:
					int seeValue=  SEE.see(state, move, state.color); //  captures either get a zero value for no good, or a value from 25 to 975
					if (seeValue!=0) {

						newValue=seeValue/25;    // now it is from 0 to 39.  39 is Best, so it short sort LOW
						newValue2=40-newValue;
						movelist[i] = Move2.setOrderingValue ( move, newValue2);
						//goodCaptures[ptr++]=movelist[i];
					}
					else {
						movelist[i]=0;
						//movelist[i] = Move2.setOrderingValue ( move, 63);
					}
					break;
				}
			}
		}

		Util.sort(movelist);
	}
	private static boolean isCapture(int moveType) {
		switch (moveType) {
		case Move2.captureNoPromotion: 
		case Move2.capturePromotionQueen:
		case Move2.epCapture:
			return true;   
		default : return false;
		}

	}
	/*private static void error(GameState gs, GameState state, int move) {
		if (!gs.equals(state)) {
			System.out.println("error");
			for (int i=0; i < 64; i++) {
				if (gs.board[i] != state.board[i] ) {
					System.out.println(" error at board i = " + i);
					System.out.println("gs.board[i]" + gs.board[i]);
					System.out.println("state.board[i]" + state.board[i]);
				}
			}
		}
		
		System.out.println(Move2.toString(move));
		gs.print();
		state.print();
		//System.exit(1);
	}
	private static void printMovelist(GameState state, int[] movelist) {
		state.print();
		for (int i=0; i< movelist.length; i++)
		{
			int move = movelist[i];
			
			System.out.println("move " + Move2.toString(move));
		}	
		System.out.println("--------------------");
	}*/
	public static  void setUsingTime(boolean b) {
		// TODO Auto-generated method stub
		usingTime=b;
	}
	

}
